package done.easy_101_200;

import com.study.common.TreeNode;
import lombok.extern.slf4j.Slf4j;
import org.junit.Test;

/**
 * 108. Convert Sorted Array to Binary Search Tree
 * 将【有序数组】转化为【平衡二叉搜索树】
 * <p>
 * 将一个按照升序排列的有序数组，转换为一棵高度平衡二叉搜索树。
 * 本题中，一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。
 * <p>
 * 示例:
 * 给定有序数组:
 * [-10,-3,0,5,9],
 * 答案：
 * [0,-10,5,null,-3,null,9]
 * <p>
 * 0
 * /   \
 * -10    5
 * / \   / \
 * nil -3 nil 9
 * <p>
 * 2019-03-24 4:56 PM
 **/
@Slf4j
public class ConvertSortedArrayToBinarySearchTree {

    @SuppressWarnings("all")
    public TreeNode sortedArrayToBST(int[] nums) {
        // 190408 first
        return null;
    }

    @Test
    public void test() {
        int[] nums = new int[]{-10, -3, 0, 5, 9};
        TreeNode root = sortedArrayToBST(nums);
//        log.info("{}", root.val);
//        log.info("{}", root.left.val);
//        log.info("{}", root.right.val);
        log.info("result:{}", root);
    }
}



























/*
public TreeNode sortedArrayToBST(int[] nums) {
    // 左右等分建立左右子树，中间节点作为子树根节点，递归该过程
    if (nums == null) return null;
    return buildTree(nums, 0, nums.length - 1);
}

private TreeNode buildTree(int[] nums, int l, int r) {
    if (l > r) {
        return null;
    }
    // 取中间值坐标
    int m = l + (r - l) / 2;

    // 先把中间值给当前节点
    TreeNode root = new TreeNode(nums[m]);

    // 递归左子树
    root.left = buildTree(nums, l, m - 1);

    // 递归左子树
    root.right = buildTree(nums, m + 1, r);
    return root;
}
*/
